1. Technical Field
The present invention relates in general to improved information storage systems, and in particular to a method and system for enhanced scheduling of read or write requests to an information storage system.
2. Description of the Related Art
Modern computer applications require large amounts of data. In many applications, this data must be retrieved from an information storage system, such as a computer disk drive system. Such disk drive systems increasingly limit performance in many computer systems, creating complexity and performance bottlenecks. It is typically the mechanical nature of computer disk drives, tape systems and other information storage systems, which fails to track the performance enhancements of modern day computer systems, as a result of the mechanical positioning aspects of such systems.
Consequently, modern computer system applications, typically utilizing a moving-head disk drive, have begun to attempt to schedule requests from the information storage system in a manner which minimizes the impact of these storage systems on the computer system performance.
A number of disk scheduling algorithms are discussed in the literature and utilized in modern commercial systems. These disk scheduling algorithms typically fall into two categories: Non-Real-Time algorithms and Real-Time algorithms.
Non-Real-Time algorithms do not take into account any time constraint associated with a request from a data storage system. A simple example of such a system is the so-called First-Come-First-Serve (FCFS) algorithm utilized in early systems which do not experience large amounts of input/output traffic.
A SCAN algorithm, also known as the “elevator” algorithm, moves the mechanical arm in an information storage system in one direction and services all requests which lie in that direction until no requests are remaining. The mechanical arm then changes its SCAN direction and repeats the operation, servicing all requests which can be served in the other direction. This algorithm has the advantage of reducing disk seek times; however, if a request arrives for data at one end of a disk and the arm has recently passed that section of the disk, a long wait time will result.
Circular SCAN (C-SCAN) is a variation of a SCAN algorithm in which the mechanical arm always scans in the same direction. Thus, after serving the last request in the SCAN direction, the arm returns to a start position without servicing any requests and begins scanning in that direction again. This algorithm provides a more uniform wait time for input/output requests.
The Shortest-Seek-Time-First (SSTF) algorithm selects the requests which will require the minimum seek time from the current arm position. Since seek-time is proportional to the number of tracks which the arm crosses, this algorithm is implemented by moving the head to the closest track in the request queue. While this algorithm might seem to reduce overall seek-time of all requests, it periodically suffers from the starvation problem for those requests which are furthest away from the current arm position.
The Shortest-Positioning-Time-First (SPTF) algorithm selects the requests with the shortest input/output time, including both seek and rotational latency. This algorithm typically includes two variations, the grouped variation or the weighted variation. These variations were proposed to solve the starvation problem associated with the original Shortest-Time-First algorithm. They are typically applied in an environment where the input/output queue length is assumed to be very long.
Finally, a Group Sweeping Scheme (GSS) permits many requests to be serviced in a service round by partitioning the requests into groups where each group is served in a fixed order within the round. The SCAN algorithm is applied within each group and the number or groups or the group size may be tuned to achieve a better performance. Each of these Non-Real-Time algorithms is fully described in the literature.
Real-Time algorithms have been proposed for scheduling information storage system accesses to achieve Real-Time retrieval. These algorithms take into account time constraints which are associated with particular input/output requests for service.
Among the Real-Time algorithms is Earliest-Deadline-First (EDF) which is an algorithm originally designed for processor scheduling. When applied to disk, the algorithm simply selects the request with the earliest deadline for service. An advantage of this algorithm is that is simple to implement; however, a weakness of this algorithm is that the algorithm does not consider the arm position to perform any seek optimization. Consequently, the disk system spends a substantial portion of time seeking, resulting in reduced throughput.
A variation of this technique is the Feasible-Deadline-SCAN (FD-SCAN) algorithm which is proposed for a real-time transaction processing and in which the track location of the request with earliest feasible deadline is utilized to determine the SCAN direction. A deadline is considered “feasible” if that deadline can be met. At each scheduling point in such an algorithm, all requests are examined to determine which has the earliest feasible deadline.
More recently, an algorithm known as “Deadline Sensitive SCAN” (DS-SCAN) has been proposed as a hybrid of the traditional EDF and SCAN algorithms. The main feature of this algorithm is that, whenever possible, it closely imitates that behavior of the SCAN algorithm in order to increase the effect of throughput of a disk, subject to the constraints, that deadline Real-Time requirements are not missed.
Upon review of the art, those skilled in this area will appreciate that the efficiency of scheduling input/output operations to an information storage system continues to be a limiting factor in computer performance.